package algorithms.paixu;

import edu.princeton.cs.algs4.Queue;

import static edu.princeton.cs.algs4.StdIn.isEmpty;

/**
 * @功能
 * @创建时间 2021/1/9
 * 二分查找（基于有序数组
 */
public class BinarySearchST<Key extends Comparable<Key>,Value> {
    private Key[] keys;
    private Value[] vals;
    private int N;

    public BinarySearchST(int capacity) {
        this.keys = (Key[])new Comparable[capacity];
        this.vals = (Value[])new Object[capacity];
    }
    public int size(){
        return N;
    }
    public Value get(Key key){
        if(isEmpty()) return null;
        int i = rank(key);
        if(i < N && keys[i].compareTo(key) == 0) return vals[i];
        else                                     return null;
    }

    /**
     * 二分查找
     * @param key
     * @return
     */
    public int rank(Key key){
        int lo = 0, hi = N - 1;
        while (lo <= hi){
            int mid = lo + (hi - lo)/2;
            int cmp = key.compareTo(keys[mid]);
            if(cmp<0) hi = mid - 1;
            else if(cmp>0) lo = mid + 1;
            else return mid;
        }
        return lo;
    }

    public void put(Key key,Value val){
        int i = rank(key);
        if(i<N&&keys[i].compareTo(key)==0){
            vals[i]=val;
            return;
        }
        for (int j=N;j>i;j--){
            keys[j]=keys[j-1];
            vals[j]=vals[j-1];
        }
        keys[i]=key;
        vals[i]=val;
        N++;
    }

    /**
     * 删除键key
     * @param key
     */
    public void delete(Key key){
        int i = rank(key);
        //数据前移
        for (int j = i; j < N -1&&vals[i]!=null; j++) {
            vals[j]=vals[j+1];
            keys[j]=keys[j+1];

        }
        //最后一位置空防止游离
        vals[N-1]=null;
        keys[N-1]=null;


    }
    public Key min(){
        return keys[0];
    }

    public Key max(){
        return keys[N-1];
    }

    public Key select(int k){
        return keys[k];
    }

    public Key ceiling(Key key){
        int i = rank(key);
        return keys[i];
    }

    /**
     * 小于等于key的最大键
     * @param key
     * @return
     */
    public Key floor(Key key){
        if(key.compareTo(keys[N-1])>0)
            return keys[N-1];
        else
            return keys[rank(key)];
    }

    public Iterable<Key> keys(Key lo,Key hi){
        Queue<Key> q = new Queue<Key>();
        for (int i = rank(lo); i <rank(hi) ; i++)
            q.enqueue(keys[i]);
            if(contains(hi))
                q.enqueue(keys[rank(hi)]);
            return q;



    }
    public boolean contains(Key key){
        return rank(key)>=0;
    }
}
